package com.Algorithm.dac;

/**
 * 汉诺塔
 * @author MaoLin Wang
 * @date 2019/11/1419:47
 */
public class Hanoitower {
    public static void main(String[] args) {
        hanoitower(4,'A','B','C');
        System.out.println(count);
    }

    static int count=0;
    /**
     * 分治算法 移动汉诺塔
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoitower(int num,char a,char b ,char c){
        //如果只有一个盘

        if (num==1){
            count++;
            System.out.println("第一个盘从"+a+"->"+c);
        }else {
            //num>=2，可以将其看做两个盘  第一个盘是最下面的一个盘，上面的所有盘看做是第二个盘
            //1.把最上面的所有盘从a ->b,移动过程会使用到c
            hanoitower(num-1,a,c,b);
            //2.把最下边的盘A->C
            count++;
            System.out.println("第"+num+"个盘从 "+a+"->"+c);
            //3.把B塔的所有盘移动到C，移动过程使用到A
            hanoitower(num-1,b,a,c);
        }
    }
}
